916. Интересное произведение

Определите все возможные значения произведения i * j, если целочисленные значения переменных i и j изменяются соответственно в диапазонах i от a до b и j от c до d (1 ≤ a, b, c, d ≤ 10).

Вход. В одной строке заданы четыре целых числа a, b, c и d (a может быть больше b, c может быть больше d).

Выход. Выведите количество возможных уникальных значений произведения.

Пример входа 1	Пример выхода 1
1 10 1 10	42
Пример входа 2	Пример выхода 2
4 2 5 2	9

РЕШЕНИЕ

cтруктура данных - map

Анализ алгоритма

Объявим структуру данных map<int, int> m, которая будет подсчитывать, сколько раз встречается произведение i * j. Количество уникальных произведений равно размеру отображения m.

Пример

Рассмотрим второй пример. Запишем таблицу умножения для матрицы [2; 4] * [2; 5].

Таблица содержит 9 различных значений.

Реализация алгоритма

Объявим структуру для хранения данных.

map<int, int> m;

Читаем входные данные.

scanf("%d %d %d %d",&a,&b,&c,&d);

Поменяем местами a и b, а также c и d, чтобы выполнялись условия a ≤ b, c ≤ d.

if (a > b) swap(a,b);

if (c > d) swap(c,d);

Перебираем все возможные произведения i * j. Для каждого произведения увеличиваем на 1 значение, связанное с ключом i * j в отображении.

for(i = a; i <= b; i++)

for(j = c; j <= d; j++)

m[i*j]++;

Выводим ответ – размер отображения m.

printf("%d\n",m.size());

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

Читаем входные данные.

int a = con.nextInt();

int b = con.nextInt();

int c = con.nextInt();

int d = con.nextInt();

Поменяем местами a и b, а также c и d, чтобы выполнялись условия a ≤ b, c ≤ d.

if (a > b) {int temp = a; a = b; b = temp;}

if (c > d) {int temp = c; c = d; d = temp;}

Объявим структуру для хранения данных.

Map<Integer,Integer> m = new HashMap<Integer,Integer>();

Перебираем все возможные произведения i * j.

for(int i = a; i <= b; i++)

for(int j = c; j <= d; j++)

{

int key = i * j;

Увеличиваем на 1 значение, связанное с ключом i * j. Если с ключом key значение еще не связано, то по умолчанию берем его равным 0.

m.put(key, m.getOrDefault(key, 0) + 1);

}

Выводим ответ – размер отображения m.

System.out.println(m.size());

con.close();

}

}

Python реализация

Читаем входные данные.

a, b, c, d = map(int, input().split())

Объявим словарь для хранения данных.

m = {}

Поменяем местами a и b, а также c и d, чтобы выполнялись условия a ≤ b, c ≤ d.

if a > b:

a, b = b, a

if c > d:

c, d = d, c

Перебираем все возможные произведения i * j. Для каждого произведения увеличиваем на 1 значение, связанное с ключом i * j в словаре.

for i in range(a, b+1):

for j in range(c, d+1):

key = i * j

m[key] = m.get(key, 0) + 1

Выводим ответ – размер словаря m.

print(len(m))